/*
 *  bfs.c
 *  
 *  Genera una BFS a partir de una Network y encuentra el camino
 *  de longitud minima al destino (trash) desde el origen (source)
 *
 */

#include <stdlib.h>
#include <stdio.h>
#include "bfs.h"
#include "../network/network.h"
#include "../network/tuple.h"

/* En la posicion 0 del arreglo se guarda la cantidad de hijos del nodo */
#define NUM_CHILDREN children[0]

/* Tipos booleanos */
#define FALSE 0
#define TRUE !FALSE

/** Estructura de la BFS */
struct sBFS
{
    /** Nombres de los nodos en la BFS representado en arreglo */
	Node *nodes;		
    /** Posiciones de los padre de los nodos */
	long int *nodes_fathers;
	/** Tamano del arreglo */
	long int size;		
    /** Indice de la ultima posicion utilizada */
	long int used;
};

long int min (long int a, long int b);

/** Genera una BFS y el camino mínimo de un Network. Devuelve un arreglo donde:
 * [0] = longitud del camino,
 * [1] = capacidad del flujo,
 * [2..n] = camino mínimo.
 */
long int* BFS_minimum_path(Network net)
{
	BFS bfs;
	Node current_node;
    Node node_son;
	long int current_node_index = 0;
	Node *children = NULL;
	long int i = 0;
	long int j = 0;
	long int *tmp_path = NULL;
	long int *final_path = NULL;
    long int flow = -1;
	int trash_found = FALSE;
	
	/* Inicializacion de la estructura BFS */
	bfs.nodes = (Node *) calloc (1, sizeof(Node));
	bfs.nodes_fathers = (long int*) calloc (1, sizeof(long int));
	bfs.size = 1;
	bfs.used = 1;
    /* En caso de memoria insuficiente */
	if (bfs.nodes == NULL || bfs.nodes_fathers == NULL)
    {
        printf("Memoria insuficiente");
		exit (EXIT_FAILURE);
    }
    
	/* La raiz de la BFS es el nodo Source, obtener el nodo, y agregarlo
	 * El algoritmo toma como punto de inicio este nodo
	 */
	current_node = network_source_node(net);
	bfs.nodes[current_node_index] = current_node;
	
	/* Ciclo principal del algoritmo BFS
	 * Cuando se haya agregado al nodo Trash termina el ciclo
	 */
	while (!trash_found)
	{
		/* Obtener los vecinos del nodo corriente */
		children = network_get_neighbours(net, current_node);
		
		/* Verificar si el tamano actual del arreglo BFS alcanza para agregar los nodos
		 * De no alcanzar, aumentar el arreglo
		 */
        if (children != NULL && current_node != network_trash_node(net)) 
        {
            if (bfs.size - bfs.used <= NUM_CHILDREN)
            {
                bfs.size += NUM_CHILDREN;
                bfs.nodes = (Node *) realloc (bfs.nodes, bfs.size * sizeof(Node));
                if(bfs.nodes == NULL){
                    printf("Memoria insuficiente\n");
                    exit(EXIT_FAILURE);
                }
                bfs.nodes_fathers = (long int *) realloc (bfs.nodes_fathers, bfs.size * sizeof(long int));
                if(bfs.nodes==NULL){
                    printf("Memoria insuficiente\n");
                    exit(EXIT_FAILURE);
                }
            }
            
            /* Agregar los hijos del nodo en el BFS */
            for (i = 1; i <= NUM_CHILDREN; i++)
            {
                /* Agregar el nodo en el primer arreglo BFS 
                 * y guardar referencia de su padre en el segundo
                 */
                
                bfs.nodes[bfs.used] = children[i];
                bfs.nodes_fathers[bfs.used] = current_node_index;
                
                if (children[i] == network_trash_node(net))
                {
                    current_node = network_trash_node(net);
                    current_node_index = bfs.used;
                    trash_found = TRUE;
                    break;
                }
                bfs.used++;
            }
        }
        else
        {
            free(bfs.nodes);
            free(bfs.nodes_fathers);
            return NULL;
        }

        
        /* Desplazarse al siguiente elemento del BFS en caso de no encontrar el trash*/
        if (!trash_found)
        {
            current_node_index++;
            current_node = bfs.nodes[current_node_index];
            free(children);
        }
    }
        
    
    if (current_node == network_trash_node(net))
    {
        /* En el peor de los casos, la longitud del path sera igual al
         * tamano usado del BFS (este seria un BFS donde cada nodo tenga
         * un solo vecino y asi se llega al nodo Trash)
         */
        
        tmp_path = calloc (bfs.used + 1, sizeof(long int));
        tmp_path[0] = current_node;
        
        i = 1;
        
        node_son = current_node;
        current_node_index = bfs.nodes_fathers[current_node_index];
        current_node = bfs.nodes[current_node_index];
        flow = network_get_capacity(net, current_node, node_son);
        tmp_path[i] = current_node;
        
        i++;
        
        while (current_node != network_source_node(net))
        {
            node_son = current_node;
            current_node_index = bfs.nodes_fathers[current_node_index];
            current_node = bfs.nodes[current_node_index];
            flow = min(flow, network_get_capacity(net, current_node, node_son));
            tmp_path[i] = current_node;
            i++;
        }

            /* El arreglo tmp_path queda con espacios vacios al final
             * y en orden inverso.
             * Se crea otro arreglo final_path en el orden correcto y de
             * tamano adecuado
             */
        final_path = calloc (i + 2, sizeof(long int));
        final_path[0] = i;
        final_path[1] = flow;
		for (j = 2; j <= i + 1; j++)
		{
			final_path[j] = tmp_path[i - j + 1];
		}
        
	}
	
	/* Liberar la memoria */
	free(bfs.nodes);
	free(bfs.nodes_fathers);
    if (children != NULL)
        free(children);
	free(tmp_path);
	    
	return final_path;
}


long int min (long int a, long int b)
{
    if (a < b)
    {
        return a;
    }
    else 
    {
        return b;
    }
}

